1. Field of the Invention
The present invention relates to a discrete cosine transformation (DCT) system and an inverse discrete cosine transformation (IDCT) system used for digital image processing etc.
2. Description of the Related Art
A discrete cosine transformation (DCT) is a type of an of orthogonal transformation which performs a transformation of data in a real domain to data in a frequency domain. An inverse discrete cosine transformation (IDCT) is also a type of an orthogonal transformation which performs a transformation inverse to the DCT, that is, performs a transformation of data in a frequency domain to data in a real domain. The DCT and the IDCT, for example, are used for image signal processing etc. An 8 row.times.8 column DCT and an 8 row.times.8 column IDCT may be expressed by the following basic (standard) equations 1 and 2: EQU DCT:[C]=1/2[P.sub.0 ][X] (1) EQU IDCT:[X]=1/2[P.sub.0.sup.t ][C] (2)
Here, [X] donates an 8 row.times.8 column original matrix data in a real domain. [C] denotes an 8 row.times.8 column matrix data in a frequency domain. [P.sub.0 ] donates an 8 row.times.8column matrix, and [P.sub.0.sup.t ] denotes a transposition matrix of the matrix [P]. Hereinafter, the suffices t on the left top of matrices indicate a transposition matrix.
The matrix [P.sub.0 ] is defined by the following equation 3. ##EQU1##
The coefficients (factors) A, B, C, D, E, F, and G in the matrix [P] are shown in Table 1.
TABLE 1 ______________________________________ A = cos (.pi./4) B= cos (.pi./8) C= cos (3.pi./8) D= cos (.pi./16) E= cos (3.pi./16) F= cos (5.pi./16) G= cos (7.pi./16) ______________________________________
When obtaining the components of the matrix [C] in a frequency domain by eight multiplications each, the computation processing of the 8.times.8 DCT expressed by the above-mentioned equation 1 requires 8.times.64=512 multiplications to obtain all the 64 components of the matrix [C].
Further, in the computation processing of the 8.times.8 IDCT as well, when obtaining the components of the original data [X] in a real domain by eight multiplications each, 8.times.64=512 multiplications are required to obtain all the 64 components of the data [X].
Proposals have been made of circuits which can reduce the number of multiplications in the computation processing of the 8.times.8 DCT and 8.times.8 IDCT, and perform the calculations of the 8.times.8 DCT and 8.times.8 IDCT at a high speed.
For example, in an 8.times.8 DCT circuit and 8.times.8 IDCT circuit shown on pages 492 to 498 of the IEEE JOURNAL OF SOLID-STATE CIRCUITS, VOL. 27, NO. 4, APRIL 1992, the preprocessing (addition and subtraction) is performed on the eight inputs, then eight fourth-order inner product computation units are used to obtain the eight outputs. This operation is repeated eight times to obtain the 64 outputs.
For example, a look at one element c.sub.0 of the matrix [C] in equation 1 shows that the equation for obtaining c.sub.0 becomes as shown in the following equation 4. Here, x.sub.0 to x.sub.7 are elements of the matrix [X]. EQU c.sub.0 =A(x.sub.0 +x.sub.7)+A(x.sub.1 +x.sub.6)+A(x.sub.2 +x.sub.5)+A(x.sub.3 +x.sub.4) (4)
In equation 4, four multiplications are necessary to obtain c.sub.0, i.e., multiplications of A and (x.sub.0 +x.sub.7) , A and (x.sub.1 +x.sub.6), A and (x.sub.2 +x.sub.5), and A and (x.sub.3 +x.sub.4). Therefore, the number of multiplications required for obtaining all the 64 elements of the matrix [C] becomes 4.times.64=256.
When performing the IDCT in accordance with equation 2,256 multiplications are needed to obtain all the 64 elements of the matrix [X].
In the above-mentioned conventional 8.times.8 DCT and the 8.times.8 IDCT mentioned above, however, while the number of multiplications is reduced, 256 multiplications still must be performed. This suffers from the disadvantage of a long operation time.
Also, if such a large number of multiplications are performed by circuits, the number of multiplication circuits, which have more complicated circuit structures than addition circuits or subtraction circuits, becomes larger and therefore, it also suffers from the disadvantage that the circuit structures of the 8.times.8 DCT circuit and 8.times.8 IDCT circuit become extremely complicated.
Further, if a large number of computations involving irrational numbers are performed, the error caused due to the approximation of irrational numbers accumulates and therefore, it further suffers from the disadvantage that the accuracy of the result of the calculation is degraded.